from typing import List


class Solution:
    # 注意 i > begin 而不是 i > 0:
    #     我们允许跨层之间使用相同的数字，而禁止同层之间相同数字
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        n = len(candidates)
        candidates.sort()

        def dfs(path, begin, target):
            if target == 0:
                res.append(path[:])
                return
            for i in range(begin, n):
                if i > begin and candidates[i-1] == candidates[i]:
                    continue
                if target - candidates[i] < 0:
                    break
                path.append(candidates[i])
                dfs(path, i+1, target-candidates[i])
                path.pop()

        dfs(path=[], begin=0, target=target)
        return res
